1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to the efficient implementation of an index structure for multi-column bi-directional searches.
2. Description of Related Art
Data in an Relational DataBase Management System (RDBMS) is organized into one or more tables that are comprised of rows and columns of data, wherein the rows are records and the columns are attributes. A database will typically have many tables and each table will typically have multiple records and multiple attributes. Users formulate relational operations on the tables, rows and columns, either interactively, in batch files, or embedded in host languages, such as C and COBOL.
It is common for indexes to be used to search the records and attributes in a table. Generally, indexes are comprised of values from one or more columns from the table with pointers to the rows in the table associated with those columns. It may be necessary for applications to specify different orderings of columns in the result table. However, to be performed efficiently, this database operation usually requires that the index be created in manner that supports such orderings, especially where the index is comprised of multiple columns of attributes from the table, and the index search is performed in an ascending manner on one column and in a descending manner on another column. Otherwise, sorting may be necessary, which is an expensive function.
There remains, however, a need in the art for new techniques for creating indexes for data files, especially indexes that are flexible in the manner in which they can be searched. The present invention provides these needed techniques.